//文件压缩-Huffman实现
#include  <stdio.h>
#include  <string.h>
#include  <stdlib.h>

#define  MAXSIZE  32

struct tnode {                        //Huffman树结构
    char c;
    int weight;                //树节点权重，叶节点为字符和它的出现次数
    struct tnode *left, *right;
};
int Ccount[128] = {0};                //存放每个字符的出现次数，如Ccount[i]表示ASCII值为i的字符出现次数
struct tnode *Root = NULL;          //Huffman树的根节点
char HCode[128][MAXSIZE] = {{0}};  //字符的Huffman编码，如HCode['a']为字符a的Huffman编码（字符串形式）
int Step = 0;                        //实验步骤
FILE *Src, *Obj;

int cmp();

void statCount();                //步骤1：统计文件中字符频率
void createHTree();                //步骤2：创建一个Huffman树，根节点为Root
void makeHCode();                //步骤3：根据Huffman树生成Huffman编码
void atoHZIP();                  //步骤4：根据Huffman编码将指定ASCII码文本文件转换成Huffman码文件

void print1();                        //输出步骤1的结果
void print2(struct tnode *p);        //输出步骤2的结果
void print3();                        //输出步骤3的结果
void print4();                        //输出步骤4的结果

int main() {
    setbuf(stdout, NULL);
    if ((Src = fopen("input.txt", "r")) == NULL) {
        fprintf(stderr, "%s  open  failed!\n", "input.txt");
        return 1;
    }
    if ((Obj = fopen("output.txt", "w")) == NULL) {
        fprintf(stderr, "%s  open  failed!\n", "output.txt");
        return 1;
    }
    scanf("%d", &Step);                //输入当前实验步骤

    statCount();                        //实验步骤1：统计文件中字符出现次数（频率）
    (Step == 1) ? print1() : 1;              //输出实验步骤1结果
    createHTree();                        //实验步骤2：依据字符频率生成相应的Huffman树
    (Step == 2) ? print2(Root) : 2;          //输出实验步骤2结果
    makeHCode();                //实验步骤3：依据Root为树的根的Huffman树生成相应Huffman编码
    (Step == 3) ? print3() : 3;              //输出实验步骤3结果
    (Step >= 4) ? atoHZIP(), print4() : 4;//实验步骤4：据Huffman编码生成压缩文件，并输出实验步骤4结果

    fclose(Src);
    fclose(Obj);
    return 0;
}


//【实验步骤1】开始

void statCount() {
    Ccount[0] = 1;//结束符
//    char *fbuf = (char *) malloc(sizeof(char) * 10240);
//    fread(fbuf, sizeof(char), 10240, Src);
//    while (*fbuf != '\0' && *fbuf != EOF) {
//        Ccount[*fbuf++]++;
//    }

    char c = fgetc(Src);
    while (c != EOF && c != '\0' && !feof(Src)) {
        Ccount[c]++;
        c = fgetc(Src);
    }
}
//【实验步骤1】结束

//【实验步骤2】开始
int cmp(const void *a, const void *b) {
    struct tnode ta = **(struct tnode **) a, tb = **(struct tnode **) b;
    if (ta.weight > tb.weight)
        return 1;
    else if (ta.weight < tb.weight)
        return -1;
    else if (ta.c > tb.c)
        return 1;
    else
        return -1;
}

void createHTree() {
    struct tnode *tree[1024];
    int cnt = 0, st = 0, pos;
    for (int i = 0; i < 128; i++) {
        if (Ccount[i] > 0) {
            struct tnode *p = (struct tnode *) malloc(sizeof(struct tnode));
            if (p == NULL) return;
            p->c = i;
            p->weight = Ccount[i];
            p->left = p->right = NULL;
            tree[cnt++] = p;
        }
    }
    qsort(tree, cnt, sizeof(struct tnode *), cmp);
//    for (int i = 0; i <= cnt; i++)
//        printf("%c : %d\n", tree[i]->c, tree[i]->weight);
    while (st < cnt - 1) {
        struct tnode *t = (struct tnode *) malloc(sizeof(struct tnode *));
        if (t == NULL) return;
        t->c = -1;
        t->weight = tree[st]->weight + tree[st + 1]->weight;
        t->left = tree[st++];
        t->right = tree[st++];
        for (pos = st; pos < cnt; pos++)
            if (tree[pos]->weight > t->weight)
                break;
        for (int i = cnt; i > pos; i--)
            tree[i] = tree[i - 1];
        tree[pos] = t;
        ++cnt;
    }
    Root = tree[st];
}



//【实验步骤2】结束

//【实验步骤3】开始
void vis(struct tnode *node, char code[]) {
    if (node == NULL) return;
    if (node->c != -1)
        strcpy(HCode[node->c], code);
    char lcode[128], rcode[128];
    for (int i = 0; i < strlen(code); i++)
        lcode[i] = rcode[i] = code[i];
    lcode[strlen(code)] = '0';
    rcode[strlen(code)] = '1';
    lcode[strlen(code) + 1] = '\0';
    rcode[strlen(code) + 1] = '\0';
    vis(node->left, lcode);
    vis(node->right, rcode);
}

void makeHCode() {
    vis(Root, "");
}
//【实验步骤3】结束

//【实验步骤4】开始
void atoHZIP() {
    char c, fbuf[4096], *p;
    rewind(Src);
    while (1) {
        c = fgetc(Src);
        if (c == EOF) {
            strcat(fbuf, HCode[0]);
            break;
        } else
            strcat(fbuf, HCode[c]);
    }
    for (int i = 0; strlen(fbuf) % 8 > 0 && i < 8 - strlen(fbuf) % 8; i++)
        strcat(fbuf, "0");
    for (unsigned int i = 0, hc; fbuf[i] != '\0'; i++) {
        hc = (hc << 1) | (fbuf[i] - '0');
        if ((i + 1) % 8 == 0) {
            fputc(hc, Obj);     //输出到目标（压缩）文件中
            printf("%x", hc);   //按十六进制输出到屏幕上
            hc = 0;
        }
    }
}
//【实验步骤4】结束

void print1() {
    int i;
    printf("NUL:1\n");
    for (i = 1; i < 128; i++)
        if (Ccount[i] > 0)
            printf("%c:%d\n", i, Ccount[i]);
}

void print2(struct tnode *p) {
    if (p != NULL) {
        if ((p->left == NULL) && (p->right == NULL))
            switch (p->c) {
                case 0:
                    printf("NUL  ");
                    break;
                case ' ':
                    printf("SP  ");
                    break;
                case '\t':
                    printf("TAB  ");
                    break;
                case '\n':
                    printf("CR  ");
                    break;
                default:
                    printf("%c  ", p->c);
                    break;
            }
        print2(p->left);
        print2(p->right);
    }
}

void print3() {
    int i;

    for (i = 0; i < 128; i++) {
        if (HCode[i][0] != 0) {
            switch (i) {
                case 0:
                    printf("NUL:");
                    break;
                case '  ':
                    printf("SP:");
                    break;
                case '\t':
                    printf("TAB:");
                    break;
                case '\n':
                    printf("CR:");
                    break;
                default:
                    printf("%c:", i);
                    break;
            }
            printf("%s\n", HCode[i]);
        }
    }
}

void print4() {
    long int in_size, out_size;

    fseek(Src, 0, SEEK_END);
    fseek(Obj, 0, SEEK_END);
    in_size = ftell(Src);
    out_size = ftell(Obj);

    printf("\n原文件大小：%ldB\n", in_size);
    printf("压缩后文件大小：%ldB\n", out_size);
    printf("压缩率：%.2f%%\n", (float) (in_size - out_size) * 100 / in_size);
}
